#ifndef _STRING_H
#include<string.h>
#endif
#ifndef _STDIO_H
#include<stdio.h>
#endif
#ifndef _STDLIB_H
#include<stdlib.h>
#endif


typedef unsigned int uint;

//打表式获取宏参个数[注意##判空参去前逗号]
#define COUNT_ARGS_HELPER(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _N, _VA_ARGS_...) _N
#define COUNT_ARGS(_VA_ARGS_...) COUNT_ARGS_HELPER(,##_VA_ARGS_, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

//变量库
int pq;
char*E1,*E2,cc;
//含结束符的字符串输入,文件结束时返回-1,否则返回长度
#define read_alpha(STRING,STREAM) ({pq=0;do{*(STRING+pq)=fgetc(STREAM);if(*(STRING+pq)==-1){pq=-1;break;}}while(((*(STRING+pq)-0x41)^(*(STRING+pq)-0x5b)^(*(STRING+pq)-0x61)^(*(STRING+pq)-0x7b))>=0);if(~pq)do{pq++;*(STRING+pq)=fgetc(STREAM);}while(((*(STRING+pq)-0x41)^(*(STRING+pq)-0x5b)^(*(STRING+pq)-0x61)^(*(STRING+pq)-0x7b))<0);*(STRING+pq)=0;pq;})

//含结束符的小写字符串输入,文件结束时返回-1,否则返回长度
#define read_low_alpha(STRING,STREAM) ({pq=0;do{*(STRING+pq)=fgetc(STREAM);if(*(STRING+pq)==-1){pq=-1;break;}}while(((*(STRING+pq)-0x41)^(*(STRING+pq)-0x5b)^(*(STRING+pq)-0x61)^(*(STRING+pq)-0x7b))>=0);if(~pq)do{if(*(STRING+pa)<0x61)*(STRING+pq)+=0x20;pq++;*(STRING+pq)=fgetc(STREAM);}while(((*(STRING+pq)-0x41)^(*(STRING+pq)-0x5b)^(*(STRING+pq)-0x61)^(*(STRING+pq)-0x7b))<0);*(STRING+pq)=0;pq;})

//含结束符的小写字符串输入,文件结束时返回-1,否则返回长度
#define read_up_alpha(STRING,STREAM) ({pq=0;do{*(STRING+pq)=fgetc(STREAM);if(*(STRING+pq)==-1){pq=-1;break;}}while(((*(STRING+pq)-0x41)^(*(STRING+pq)-0x5b)^(*(STRING+pq)-0x61)^(*(STRING+pq)-0x7b))>=0);if(~pq)do{if(*(STRING+pa)>0x5a)*(STRING+pq)-=0x20;pq++;*(STRING+pq)=fgetc(STREAM);}while(((*(STRING+pq)-0x41)^(*(STRING+pq)-0x5b)^(*(STRING+pq)-0x61)^(*(STRING+pq)-0x7b))<0);*(STRING+pq)=0;pq;})

//TODO:读入int型
#define read_digit(NUM,STREAM) ({do{cc=fgetc(STREAM);}while(~cc&&((cc-0x30)^(cc-0x3a))>0);if(~cc){(NUM)=cc-0x30;while(~(cc=fgetc(STREAM))&&((cc-0x30)^(cc-0x3a))<0)(NUM)=(NUM)*10+cc-0x30;cc=1;}cc;})

#define digital(x) ((((x)-0x30)^((x)-0x3a))<0)
#define alphabet(x) (((((x)-0x41)^((x)-0x5b))<0)|(((((x)-0x61)^((x)-0x7b))<0)<<1))//小写为2,大写为1,否则为0
#define Tolower(x) (x|0x20)
#define Toupper(x) (x&~0x20)
#define toint(c) ((c&0x1f)-1)//大小写字母变编号
#define swap(x,y) ({if(&x!=&y){(x)^=(y);(y)^=(x);(x)^=(y);}})//等长int之间的交换
#define min(x,y) ((y)^(((x)^(y))&-((x)<(y))))
#define max(x,y) ((x)^(((x)^(y))&-((x)<(y))))
#define end1to0(x) ((x)&((x)-1))//2进制末位操作
#define end0to1(x) ((x)|((x)+1))//2进制末位操作
#define ispow2(x) ((x)&&!((x)&((x)-1)))//2^n判断
#define opsign(x,y) (((x)^(y))<0)//符号判反

#define copy_size(ele1,ele2,SIZE)({E1=(char*)(&(ele1));E2=(char*)(&(ele2));if(E1!=E2){for(pq=0;pq<SIZE;pq++)*(E1+pq)=*(E2+pq);}})
#define SwapEle_Type(ele1,ele2,TYPE)({E1=(char*)(&(ele1));E2=(char*)(&(ele2));if(E1!=E2){for(pq=0;pq<sizeof(TYPE);pq++)*(E1+pq)^=*(E2+pq),*(E2+pq)^=*(E1+pq),*(E1+pq)^=*(E2+pq);}})
#define SwapEle_Size(ele1,ele2,SIZE)({E1=(char*)(&(ele1));E2=(char*)(&(ele2));if(E1!=E2){for(pq=0;pq<SIZE;pq++)*(E1+pq)^=*(E2+pq),*(E2+pq)^=*(E1+pq),*(E1+pq)^=*(E2+pq);}})


//字符串sunday匹配,返回第一个匹配上的地址或者NULL
inline char* Sunday(char*source_string,char*target_string){
    const unsigned int char_plus=128;
    unsigned int former[300]={},i=0,len_tar,j,len_sor;
    while(target_string[i]){
        former[char_plus+target_string[i]]=i+1;
        i++;
    }
    len_tar=i;i=0;
    while(source_string[i])i++;
    len_sor=i;i=0;
    if(len_sor<len_tar)return NULL;
    while(i<len_sor){
        for(j=0;j<len_tar&&source_string[i+j]==target_string[j];j++);
        if(j==len_tar)return source_string+i;
        if(!source_string[i+j])break;
        i+=len_tar;
        if(i>=len_sor)break;
        i-=former[char_plus+source_string[i]]-1;
    }
    return NULL;
}

//自变量是字符串指针和字符串数的进制以及最大翻译长度,可修改temporaruATI的类型为long
inline int atoi10_explore(char*STRING,int TRANS_RADIX,int STRING_LENGTH){
	int temporaryplace=0;int temporaryATI=0;
	if(*STRING=='-'||*STRING=='+')temporaryplace++;
	do{
		if(((*(STRING+temporaryplace)-0x30)^(*(STRING+temporaryplace)-0x30-TRANS_RADIX))<0)temporaryATI=temporaryATI*(TRANS_RADIX)+*(STRING+temporaryplace++)-0x30;
		else if(TRANS_RADIX>10){
			if(((*(STRING+temporaryplace)-0x41)^(*(STRING+temporaryplace)-0x37-TRANS_RADIX))<0)temporaryATI=temporaryATI*(TRANS_RADIX)+*(STRING+temporaryplace++)-0x37;
			else if(((*(STRING+temporaryplace)-0x61)^(*(STRING+temporaryplace)-0x57-TRANS_RADIX))<0)temporaryATI=temporaryATI*(TRANS_RADIX)+*(STRING+temporaryplace++)-0x57;
			else temporaryplace=-1;
		}
		else temporaryplace=-1;
	}while(~temporaryplace&&temporaryplace<STRING_LENGTH);
	return *STRING=='-'?-temporaryATI:temporaryATI;
}

//选择排序，依赖元素交换SwapEle_Size
inline void Selection_pro_sort(void*Araary,const unsigned int len,const unsigned int elementsize,int(*cmp_function)(const void*e1,const void*e2)){
    if(len<2)return;
    char*avaArr=(char*)(Araary),*min,*max;
    unsigned int Sesorti=0,Sesorti_j=0;
    for(;Sesorti_j<(len>>1);Sesorti_j++){
        for(max=min=avaArr+Sesorti_j*elementsize,Sesorti=Sesorti_j+1;Sesorti<len-Sesorti_j;Sesorti++){
            if(cmp_function(min,avaArr+Sesorti*elementsize)>0){
                min=avaArr+Sesorti*elementsize;
            }
            if(cmp_function(max,avaArr+Sesorti*elementsize)<0){
                max=avaArr+Sesorti*elementsize;
            }
        }
        SwapEle_Size(*min,*(avaArr+Sesorti_j*elementsize),elementsize);
        if(max!=avaArr+Sesorti_j*elementsize||min!=avaArr+(len-1-Sesorti_j)*elementsize)SwapEle_Size(*max,*(avaArr+(len-1-Sesorti_j)*elementsize),elementsize);
    }
    return;
}

//鸡尾酒排序 (冒泡排序的max plus pro版 (X 重现冒泡荣光,确信!
inline void Cocktail_sort(void*Araary,const unsigned int len,const unsigned int elementsize,int(*cmp_function)(const void*e1,const void*e2)){
    if(len<2)return;
    char*avaArr=(char*)(Araary);
    unsigned int Cosorti=0,Cosorti_back=len-1,Cosorti_front=0,Cosortinew;
    while(Cosorti_front<Cosorti_back){
        for(Cosorti=Cosorti_front;Cosorti<Cosorti_back;Cosorti++){
            if(cmp_function(avaArr+Cosorti*elementsize,avaArr+(1+Cosorti)*elementsize)>0){
                SwapEle_Size(*(avaArr+Cosorti*elementsize),*(avaArr+(1+Cosorti)*elementsize),elementsize);
                Cosortinew=Cosorti;
            }
        }
        Cosorti_back=Cosortinew;
        for(Cosorti=Cosorti_back;Cosorti>Cosorti_front;Cosorti--){
            if(cmp_function(avaArr+Cosorti*elementsize,avaArr+(Cosorti-1)*elementsize)<0){
                SwapEle_Size(*(avaArr+Cosorti*elementsize),*(avaArr+(Cosorti-1)*elementsize),elementsize);
                Cosortinew=Cosorti;
            }
        }
        Cosorti_front=Cosortinew;
    }
    return;
}

//arguments: stack length, stack element type(e.g. char short int long float double)
//attention
#define define_stack(STACK_LENTH_MAXSIZE,STACK_ELEMENT_TYPE)\
struct arongstack##_##STACK_LENTH_MAXSIZE##_##STACK_ELEMENT_TYPE{\
	STACK_ELEMENT_TYPE ELEM[STACK_LENTH_MAXSIZE];\
	unsigned int top,MAXSIZE;\
    int check;\
}
//*C语言版普通栈，用前必须Stackflush初始化
#define Stackflush(SAK,STACK_LENTH_MAXSIZE) (SAK.top=0,SAK.MAXSIZE=STACK_LENTH_MAXSIZE)
#define stack_pushback(SAK,element) ({if(SAK.top<SAK.MAXSIZE)SAK.ELEM[SAK.top++]=element,SAK.check=1;else SAK.check=0;SAK.check;})
#define stack_popup(SAK,element) ({if(SAK.top)element=SAK.ELEM[--SAK.top],SAK.check=2;else SAK.check=0;SAK.check;})
#define stack_visit(SAK,element) ({if(SAK.top)element=SAK.ELEM[SAK.top-1],SAK.check=3;else SAK.check=0;SAK.check;})
#define StackEmpty(SAK) (!SAK.top)
#define Stackfull(SAK) (SAK.top==SAK.MAXSIZE)
#define Stacklenth(SAK) (SAK.top)

// //C语言版普通栈，记得初始化
// #define STACK_LENTH_MAXSIZE (100)//修改最大栈长
// typedef int STACK_ELEMENT_TYPE; //修改栈元类型
// typedef struct arongstack{//  >读栈首
// 	STACK_ELEMENT_TYPE ELEM[STACK_LENTH_MAXSIZE];
// 	int top;
// }stack;
// int stack_pushback(stack*SAK,STACK_ELEMENT_TYPE*e){
// 	if(SAK->top>STACK_LENTH_MAXSIZE)return 0;
// 	SAK->ELEM[SAK->top++]=*e;
// 	return 1;
// }
// int stack_popup(stack*SAK,STACK_ELEMENT_TYPE*e){
// 	if(!SAK->top)return 0;
// 	*e=SAK->ELEM[--SAK->top];
// 	return 1;
// }
// int stack_visit(stack*SAK,STACK_ELEMENT_TYPE*e){
// 	if(!SAK->top)return 0;
// 	*e=SAK->ELEM[SAK->top-1];
// 	return 1;
// }
// #define StackEmpty(s) (!s.top)
// #define Stackfull(s) (s.top==STACK_LENTH_MAXSIZE)
// #define Stackflush(s) (s.top=0)
// #define Stacklenth(s) (s.top)

#define define_queue(QUEUE_LENTH_MAXSIZE,QUEUE_ELEMENT_TYPE)\
struct arongqueue##_##QUEUE_LENTH_MAXSIZE##_##QUEUE_ELEMENT_TYPE{\
	QUEUE_ELEMENT_TYPE ELEM[QUEUE_LENTH_MAXSIZE+1];\
	unsigned int front,rear,MAXSIZE;\
    int check;\
}//*C语言版普通循环队列，用前必须queueflush初始化
#define Queueflush(QEE,QUEUE_LENTH_MAXSIZE) (QEE.front=QEE.rear=0,QEE.MAXSIZE=QUEUE_LENTH_MAXSIZE)
#define queue_enqueue(QEE,element) ({if(QEE.rear!=(QEE.front+QUEUE.MAXSIZE)%(QUEUE.MAXSIZE+1))QEE.ELEM[QEE.rear++]=element,QEE.rear%=(QEE.MAXSIZE+1),QEE.check=1;else QEE.check=0;QEE.check})
#define queue_dequeue(QEE,element) ({if(QEE.rear!=QEE.front)element=QEE.ELEM[QEE.front++],QEE.front%=(QEE.MASIZE+1),QEE.check=2;else QEE.check=0;QEE.check})
#define queue_visit(QEE,element) ({if(QEE.rear!=QEE.front)element=QEE.ELEM[QEE.front],QEE.check=2;else QEE.check=0;QEE.check})
#define QueueEmpty(x) (x.front==x.rear)
#define Queuefull(x) (x.rear==(x.front+x.MAXSIZE)%(x.MAXSIZE+1))
#define Queuelenth(x) ((x.rear-x.front+x.MAXSIZE+1)%(x.MAXSIZE+1))


// //C语言循环队列
// #define QUEUE_LENTH_MAXSIZE (100)//修改队列长度
// typedef int QUEUE_ELEMENT_TYPE;//修改队列元素类型
// typedef struct arongqueue{
// 	int front,rear;
// 	QUEUE_ELEMENT_TYPE elem[QUEUE_LENTH_MAXSIZE];
// }queue;
// int queue_push(queue*QEE,QUEUE_ELEMENT_TYPE*e){
// 	if(QEE->rear==(QEE->front+QUEUE_LENTH_MAXSIZE)%(QUEUE_LENTH_MAXSIZE+1))return 0;
// 	QEE->elem[QEE->rear++]=*e;
// 	QEE->rear%=(QUEUE_LENTH_MAXSIZE+1);
// 	return 1;
// }
// int queue_pop(queue*QEE,QUEUE_ELEMENT_TYPE*e){
// 	if(QEE->rear==QEE->front)return 0;
// 	*e=QEE->elem[QEE->front++];
// 	QEE->front%=(QUEUE_LENTH_MAXSIZE+1);
// 	return 1;
// }
// int queue_visit(queue*QEE,QUEUE_ELEMENT_TYPE*e){
// 	if(QEE->rear==QEE->front)return 0;
// 	*e=QEE->elem[QEE->front];
// 	return 1;
// }
// #define QueueEmpty(x) (x.front==x.rear)
// #define Queuefull(x) (x.rear==(x.front+QUEUE_LENTH_MAXSIZE)%(QUEUE_LENTH_MAXSIZE+1))
// #define Queueflush(x) (x.rear=x.front=0)
// #define Queuelenth(x) ((x.rear-x.front+QUEUE_LENTH_MAXSIZE+1)%(QUEUE_LENTH_MAXSIZE+1))


//申请链表
inline int*checklist_produce(unsigned int lenth,const char value){
    int len=(lenth+29)/30;
    int*checklist=(int*)(calloc(len+2,sizeof(int)));
    checklist[0]=len+2;checklist[1]=2;
    if(value){
        for(unsigned int i=0;i<len-1;i++)checklist[i+2]=0x3fffffff;
        checklist[len+1]=(1<<(lenth%30))-1;
    }
    return checklist;
}
inline int*checklist_gettail1(int*checklist,unsigned int begin,unsigned int end,unsigned int num,const char dele){
    if(checklist[1]==checklist[0])return NULL;
    unsigned int begin1=(begin+30)/30+1,begin2=begin-(begin1-2)*30;
    unsigned int end1=(end+29)/30+1,end2=end-(end1-2)*30;
    int n,*place=(int*)(calloc(end-begin+1,sizeof(int)));
    begin=begin1>checklist[1]?begin1:checklist[1];
    place[0]=1;
    while(begin<=end1){
        while(begin<=end1){
            end=checklist[begin];
            if(begin==begin1)end&=~((1<<begin2)-1);
            if(begin==end1)end&=(1<<end2)-1;
            if(end)break;
            begin++;
        }
        if(begin>end1)break;
        while(end){
            n=__builtin_ctz(end);
            place[place[0]++]=n+(begin-2)*30;
            if(place[0]-1==num)return place;
            if(dele)checklist[begin]^=(1<<n);
            end^=(1<<n);
        }
        begin++;
    }
    while(checklist[1]<checklist[0]&&!checklist[checklist[1]])checklist[1]++;
    if(place[0]==1)return NULL;
    return place;
}
inline int checklist_change(int*checklist,const int index,const char manner){
    unsigned int index1=(index+30)/30+1,index2=index-(index1-2)*30;
    if(index1>=checklist[0])return 0;
    if(manner){
        checklist[index1]|=(1<<index2);
        if(checklist[1]>index1)checklist[1]=index1;
    }
    else{
        checklist[index1]^=(1<<index2);
        while(checklist[1]<checklist[0]&&!checklist[checklist[1]])checklist[1]++;
    }
    return 1;
}


int cmp_short_up(const void* e1, const void* e2){return *(short*)e1<=*(short*)e2?-1:1;}
int cmp_short_down(const void* e1, const void* e2){return *(short*)e1>=*(short*)e2?-1:1;}

int cmp_int_up(const void* e1, const void* e2){return *(int*)e1<=*(int*)e2?-1:1;}
int cmp_int_down(const void* e1, const void* e2){return *(int*)e1>=*(int*)e2?-1:1;}

int cmp_long_up(const void* e1, const void* e2){return *(long*)e1<=*(long*)e2?-1:1;}
int cmp_long_down(const void* e1, const void* e2){return *(long*)e1>=*(long*)e2?-1:1;}

int cmp_longlong_up(const void* e1, const void* e2){return *(long long*)e1<=*(long long*)e2?-1:1;}
int cmp_longlong_down(const void* e1, const void* e2){return *(long long*)e1>=*(long long*)e2?-1:1;}

int cmp_ushort_up(const void* e1, const void* e2){return *(unsigned short*)e1<=*(unsigned short*)e2?-1:1;}
int cmp_ushort_down(const void* e1, const void* e2){return *(unsigned short*)e1>=*(unsigned short*)e2?-1:1;}

int cmp_uint_up(const void* e1, const void* e2){return *(unsigned int*)e1<=*(unsigned int*)e2?-1:1;}
int cmp_uint_down(const void* e1, const void* e2){return *(unsigned int*)e1>=*(unsigned int*)e2?-1:1;}

int cmp_ulong_up(const void* e1, const void* e2){return *(unsigned long*)e1<=*(unsigned long*)e2?-1:1;}
int cmp_ulong_down(const void* e1, const void* e2){return *(unsigned long*)e1>=*(unsigned long*)e2?-1:1;}

int cmp_ulonglong_up(const void* e1, const void* e2){return *(unsigned long long*)e1<=*(unsigned long long*)e2?-1:1;}
int cmp_ulonglong_down(const void* e1, const void* e2){return *(unsigned long long*)e1>=*(unsigned long long*)e2?-1:1;}

int cmp_float_up(const void* e1, const void* e2){return *(float*)e1-*(float*)e2>0.00000000001?1:-1;}
int cmp_float_down(const void* e1, const void* e2){return *(float*)e1-*(float*)e2<0.00000000001?1:-1;}

int cmp_double_up(const void* e1, const void* e2){return *(double*)e1-*(double*)e2>0.00000000001?1:-1;}
int cmp_double_down(const void* e1, const void* e2){return *(double*)e1-*(double*)e2<0.00000000001?1:-1;}

//需要<string>头文件
int cmp_str_size_up(const void* e1, const void* e2){return strcmp((char*)e1,(char*)e2)<=0?-1:1;}
int cmp_str_size_down(const void* e1, const void* e2){return strcmp((char*)e1,(char*)e2)>=0?-1:1;}

//需要<string>头文件
int cmp_str_len_up(const void* e1, const void* e2){return strlen((char*)e1)<=strlen((char*)e2)?-1:1;}
int cmp_str_len_down(const void* e1, const void* e2){return strlen((char*)e1)>=strlen((char*)e2)?-1:1;}
